Word pattern [Isomorphic Strings]

Time: O(N); Space: O(C); easy

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Example 1:

Input: pattern = “abba”, str = “dog cat cat dog”

Output: True

Example 2:

Input:pattern = “abba”, str = “dog cat cat fish”

Output: False

Example 3:

Input: pattern = “aaaa”, str = “dog cat cat dog”

Output: False

Example 4:

Input: pattern = “abba”, str = “dog dog dog dog”

Output: False

Notes:

  • You may assume pattern contains only lowercase letters, and str contains lowercase letters that may be separated by a single space.

[3]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(C),C is unique count of pattern
    """
    def wordGenerator(self, str):
        """
        Generate a word at a time without saving all the words.
        """
        w = ''
        for c in str:
            if c == ' ':
                yield w
                w = ''
            else:
                w += c
        yield w

    def wordCount(self, str):
        cnt = 1 if str else 0
        for c in str:
            if c == ' ':
                cnt += 1
        return cnt

    def wordPattern(self, pattern, str):
        """
        :type pattern: str
        :type str: str
        :rtype: bool
        """
        if len(pattern) != self.wordCount(str):
            return False

        w2p, p2w = {}, {}

        for p, w in zip(pattern, self.wordGenerator(str)):
            if w not in w2p and p not in p2w:
                # Build mapping. Space: O(c)
                w2p[w] = p
                p2w[p] = w
            elif w not in w2p or w2p[w] != p:
                # Contradict mapping
                return False
        return True

[4]:

s = Solution1()

pattern = "abba"
str = "dog cat cat dog"
assert s.wordPattern(pattern, str) == True

pattern = "abba"
str = "dog cat cat fish"
assert s.wordPattern(pattern, str) == False

pattern = "aaaa"
str = "dog cat cat dog"
assert s.wordPattern(pattern, str) == False

pattern = "abba"
str = "dog dog dog dog"
assert s.wordPattern(pattern, str) == False

[7]:

class Solution2(object):
    def wordPattern(self, pattern, str):
        """
        :type pattern: str
        :type str: str
        :rtype: bool
        """
        words = str.split()  # Space: O(n)
        if len(pattern) != len(words):
            return False

        w2p, p2w = {}, {}

        for p, w in zip(pattern, words):
            if w not in w2p and p not in p2w:
                # Build mapping. Space: O(c)
                w2p[w] = p
                p2w[p] = w
            elif w not in w2p or w2p[w] != p:
                # Contradict mapping
                return False

        return True

[8]:

s = Solution2()

pattern = "abba"
str = "dog cat cat dog"
assert s.wordPattern(pattern, str) == True

pattern = "abba"
str = "dog cat cat fish"
assert s.wordPattern(pattern, str) == False

pattern = "aaaa"
str = "dog cat cat dog"
assert s.wordPattern(pattern, str) == False

pattern = "abba"
str = "dog dog dog dog"
assert s.wordPattern(pattern, str) == False